#include "tbp_build_star.h"
#include "type.h"
#include "utils.h"
#include <cstring>
#include <queue>
#include <sstream>
#include <string>

namespace tbp {
std::vector<uint32_t> order_;

void Insert(Indexes &idx, Entry e, uint32_t vertex_id, bool in) {
  if (in) {
    std::vector<Entry> &vec = idx.label_in_[vertex_id];
    // 二分查找
    uint32_t hi = vec.size();
    uint32_t lo = 0;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      if (order_[vec[mid].id_] > order_[e.id_]) {
        hi = mid;
      } else if (order_[vec[mid].id_] == order_[e.id_]) {
        if (vec[mid].end_ < e.end_) {
          lo = mid + 1;
        } else {
          hi = mid;
        }
      } else {
        lo = mid + 1;
      }
    }
    // insert
    vec.insert(vec.begin() + lo, e);
  } else {
    std::vector<Entry> &vec = idx.label_out_[vertex_id];
    uint32_t hi = vec.size();
    uint32_t lo = 0;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      if (order_[vec[mid].id_] > order_[e.id_]) {
        hi = mid;
      } else if (order_[vec[mid].id_] == order_[e.id_]) {
        if (vec[mid].end_ < e.end_) {
          lo = mid + 1;
        } else {
          hi = mid;
        }
      } else {
        lo = mid + 1;
      }
    }
    vec.insert(vec.begin() + lo, e);
  }
}

bool Query(uint32_t u, uint32_t w, uint32_t ts, uint32_t te, Indexes &idx) {
  int i = 0, j = 0;
  auto &lin = idx.label_in_[w];
  auto &lout = idx.label_out_[u];
  while (j < lin.size() && i < lout.size()) {
    Entry eout = lout[i];
    Entry ein = lin[j];
    if (eout.id_ == w && eout.start_ >= ts && eout.end_ <= te)
      return true;
    else if (ein.id_ == u && ein.start_ >= ts && ein.end_ <= te)
      return true;
    else if (eout.id_ == ein.id_ && eout.start_ >= ts && eout.end_ <= te &&
             ein.start_ >= eout.end_ && ein.end_ <= te)
      return true;
    else if (order_[eout.id_] < order_[ein.id_])
      i++;
    else if (order_[eout.id_] > order_[ein.id_])
      j++;
    else {
      i++;
      j++;
    }
  }
  return false;
}

uint32_t FindPartNum(Partitions &partition, Entry e) {
  uint32_t v = e.id_;
  uint32_t ts = e.start_;
  uint32_t te = e.end_;
  Vertex_Partition info = partition.vertex_partition_[v];
  for (int i = 0; i < info.part_num; i++) {
    time_pair tp = info.table_[i];
    if (tp.first <= ts && tp.second >= te) {
      return i;
    }
  }
  std::cout << "分区错误\n";
  exit(-1);
  return 0;
}

void DEBUG(Partitions &partition, BiGraph &graph) {
  uint32_t num = graph.lower_size_;
  std::vector<Vertex_Partition> vec = partition.vertex_partition_;
  for (int i = 1; i <= num; i++) {
    std::stringstream ss;
    ss << "vertex: " << i << "\n";
    Vertex_Partition info = vec[i];
    ss << "分区数量: " << info.part_num << "\n";
    time_pair *edges_time = graph.Get_L_Edge_Time(i);
    uint32_t degree = graph.Get_L_Degree(i);
    uint32_t *edges = graph.lower_edges_;
    for (int j = 0; j < info.part_num; j++) {
      std::set<uint32_t> s = info.part_[j];
      ss << "分区 " << j << ":\n";
      for (auto t : s) {
        time_pair time = edges_time[t];
        uint32_t point = edges[t];
        Entry e(point, time.first, time.second);
        ss << e << " ";
      }
      ss << "\n";
    }
    ss << "map table: \n";
    for (int j = 0; j < degree; j++) {
      uint32_t point = edges[j];
      time_pair time = edges_time[j];
      Entry e(point, time.first, time.second);
      ss << e << " : " << info.map_[j] << "\n";
    }
    std::cout << ss.str() << "\n\n";
  }
}

Indexes TBP_BUILD_STAR(BiGraph &graph) {
  Timer timer;
  timer.start();
  Partitions partition = Partition_L_Edges(graph);
  // DEBUG(partition, graph);
  Indexes idx;
  auto order_vec = graph.vertex_order_; // global var
  // 方便比较order，节点i的order就是order[i]
  order_.resize(order_vec.size() + 1);
  for (int i = 0; i < order_vec.size(); i++) {
    order_[order_vec[i]] = i;
  }
  idx.resize(graph.upper_size_);

  // 用于优先队列，paper中说了pop出endtime最小的index
  auto cmp = [](const Entry &obj1, const Entry &obj2) {
    return obj1.end_ < obj2.end_;
  };

  auto cmp2 = [](const Entry &obj1, const Entry &obj2) {
    return obj1.start_ > obj2.start_;
  };
  bool *visited = new bool[graph.edge_size_];

  for (auto u : graph.vertex_order_) {
    std::cout << "id == " << u << "\n";

    // ===========================debug===========================
    Timer test_timer;
    test_timer.start();
    // ===========================debug===========================
    std::memset(visited, false, graph.edge_size_ * sizeof(bool));
    // 处理lin
    std::priority_queue<Entry, std::vector<Entry>, decltype(cmp)> que(cmp);

    std::vector<uint32_t> minT(graph.upper_size_ + 1,
                               std::numeric_limits<std::uint32_t>::max());
    std::vector<uint32_t> maxMinT(graph.lower_size_ + 1,
                                  std::numeric_limits<std::uint32_t>::max());
    minT[u] = 0;
    uint32_t *edges = graph.Get_U_Edges(u);
    uint32_t degree = graph.Get_U_Degree(u);
    time_pair *times = graph.Get_U_Edge_Time(u);

    // start time降序
    std::set<uint32_t> ss;
    std::vector<Entry> uedge(degree);
    for (int i = 0; i < degree; i++) {
      uedge[i] = Entry(i, times[i].first, times[i].second);
    }
    std::sort(uedge.begin(), uedge.end(),
              [](Entry f, Entry s) { return f.start_ > s.start_; });

    for (auto tmp : uedge) {

      // 遍历不同开始时间
      uint32_t i = tmp.id_;
      time_pair tp = times[i];
      uint32_t ts = tp.first;
      if (ss.count(ts)) {
        continue;
      } else {
        ss.insert(ts);
      }
      que.push(Entry(u, ts, ts));
      while (!que.empty()) {
        Entry e = que.top();
        que.pop();
        uint32_t w = e.id_;
        uint32_t ts_p = e.start_;
        uint32_t te_p = e.end_;
        if (w != u) {
          if (Query(u, w, ts_p, te_p, idx))
            continue;
          else {
            Insert(idx, Entry(u, ts_p, te_p), w, true);
          }
        }

        // line 15
        uint32_t *edges_w = graph.Get_U_Edges(w);
        uint32_t degree_w = graph.Get_U_Degree(w);
        time_pair *times_w = graph.Get_U_Edge_Time(w);
        uint32_t total_idx = graph.Get_UEdge_Idx(w);
        // 遍历w的边
        for (int j = 0; j < degree_w; j++) {
          // 拿到第j条边的信息
          uint32_t v = edges_w[j];
          time_pair time = times_w[j];
          if (time.first < te_p)
            continue;
          if (visited[total_idx + j])
            continue;

          visited[total_idx + j] = true;
          uint32_t t = 0;
          uint32_t t1 = time.first;
          uint32_t t2 = time.second;
          if (t1 >= maxMinT[v])
            continue;

          // 遍历这个分区,首先要找到是哪个分区
          uint32_t part_num = FindPartNum(partition, Entry(v, t1, t2));
          std::set<uint32_t> &s =
              partition.vertex_partition_[v].part_[part_num];
          // s 中记录了哪几条边目前是part num分区下的
          uint32_t *v_edges = graph.Get_L_Edges(v);
          time_pair *v_edge_time = graph.Get_L_Edge_Time(v);
          uint32_t v_degree = graph.Get_L_Degree(v);
          for (auto tt : s) {
            uint32_t x = v_edges[tt];
            uint32_t t1_p = v_edge_time[tt].first;
            uint32_t t2_p = v_edge_time[tt].second;
            if (order_[x] <= order_[u])
              continue;
            if (t2_p >= minT[x])
              continue;
            if (Is_Overlapping(v_edge_time[tt], time)) {
              que.push(Entry(x, ts_p, t2_p));
              minT[x] = t2_p;
            }
            if (minT[x] > t) {
              t = minT[x];
            }
          }
          // if (t != 0)
          maxMinT[v] = t;
        }
      }
      // ===========================debug===========================
      // test_for_timer.end();
      // std::cout << "单次start time耗时 " << test_for_timer.GetTimeConsuming()
      //           << "\n";
      // ===========================debug===========================
    }
    // ===========================debug===========================

    test_timer.end();
    std::cout << "计算 Lin 消耗" << test_timer.GetTimeConsuming() << "\n";
    test_timer.start();
    // ===========================debug===========================

    // 处理lout
    std::set<uint32_t> ss_;
    std::sort(uedge.begin(), uedge.end(),
              [](Entry f, Entry s) { return f.end_ < s.end_; });
    std::vector<uint32_t> maxT(graph.upper_size_ + 1, 0);
    std::vector<uint32_t> minMaxT(graph.lower_size_ + 1, 0);
    maxT[u] = std::numeric_limits<uint32_t>::max();
    std::memset(visited, false, graph.edge_size_ * sizeof(bool));
    std::priority_queue<Entry, std::vector<Entry>, decltype(cmp2)> que2(cmp2);
    for (auto tmp : uedge) {
      uint32_t i = tmp.id_;
      uint32_t te = tmp.end_;
      if (ss_.count(te)) {
        continue;
      } else {
        ss_.insert(te);
      }
      // q.push
      que.push(Entry(u, te, te));
      while (!que.empty()) {
        Entry e = que.top();
        que.pop();
        uint32_t w = e.id_;
        uint32_t ts_p = e.start_;
        uint32_t te_p = e.end_;
        if (w != u) {
          if (Query(w, u, ts_p, te_p, idx)) {
            continue;
          } else {
            Insert(idx, Entry(u, ts_p, te_p), w, false);
          }
        }

        // line 15
        uint32_t *edges_w = graph.Get_U_Edges(w);
        uint32_t degree_w = graph.Get_U_Degree(w);
        time_pair *times_w = graph.Get_U_Edge_Time(w);
        uint32_t total_idx = graph.Get_UEdge_Idx(w);
        // 遍历w的边
        for (int j = 0; j < degree_w; j++) {
          uint32_t v = edges_w[j];
          time_pair time = times_w[j];
          uint32_t t = std::numeric_limits<uint32_t>::max();
          uint32_t t1 = time.first;
          uint32_t t2 = time.second;

          if (visited[total_idx + j])
            continue;
          if (t2 > ts_p)
            continue;

          visited[total_idx + j] = true;
          if (t2 <= minMaxT[v])
            continue;
          uint32_t part_num = FindPartNum(partition, Entry(v, t1, t2));
          std::set<uint32_t> &s =
              partition.vertex_partition_[v].part_[part_num];
          uint32_t *v_edges = graph.Get_L_Edges(v);
          time_pair *v_edge_time = graph.Get_L_Edge_Time(v);
          uint32_t v_degree = graph.Get_L_Degree(v);
          for (auto tt : s) {
            uint32_t x = v_edges[tt];
            uint32_t t1_p = v_edge_time[tt].first;
            uint32_t t2_p = v_edge_time[tt].second;
            if (order_[x] <= order_[u])
              continue;
            if (t1_p <= maxT[x])
              continue;
            if (Is_Overlapping(v_edge_time[tt], time)) {

              que.push(Entry(x, t1_p, te_p));
              maxT[x] = t1_p;
            }
            if (maxT[x] < t) {
              t = maxT[x];
            }
          }
          // if (t != std::numeric_limits<uint32_t>::max())
          minMaxT[v] = t;
        }
      }
    }
    // ===========================debug===========================

    test_timer.end();
    std::cout << "计算 Lout 消耗" << test_timer.GetTimeConsuming() << "\n";
    // ===========================debug===========================
  }

  timer.end();
  std::cout << "build end, time = " << timer.GetTimeConsuming() << "\n";
  delete[] visited;

  return idx;
}

bool Is_Overlapping(time_pair first, time_pair second) {
  return std::min(first.second, second.second) >
         std::max(first.first, second.first);
}

Partitions Partition_L_Edges(BiGraph &graph) {
  std::cout << "begin partition\n";
  Timer timer;
  timer.start();
  uint32_t l_size = graph.lower_size_;
  Partitions res(l_size + 1);
  // 接下来遍历Lower的每一个节点

  for (int i = 1; i <= l_size; i++) {
    // 拿到第i个节点的边以及时间关系
    time_pair *edges_time = graph.Get_L_Edge_Time(i);
    uint32_t degree = graph.Get_L_Degree(i);
    // 边的范围edges[0]到edges[degree-1]
    res.vertex_partition_[i].map_.resize(degree);
    std::unordered_map<uint32_t, time_pair> &table =
        res.vertex_partition_[i].table_;
    //(第i个分区，当前维护的时间长度)
    uint32_t global_part_idx = 0;

    // 需要先排序处理，否则会造成分区数量虚高
    // 转成一个区间合并问题
    // Entry 含义id: 第几条边， 其他含义不变
    std::vector<Entry> vec;
    for (int j = 0; j < degree; j++) {
      vec.emplace_back(Entry(j, edges_time[j].first, edges_time[j].second));
    }

    // 按照从小到大排序
    std::sort(vec.begin(), vec.end(), [](Entry first, Entry second) {
      return first.start_ < second.start_;
    });

    // 遍历edge
    for (auto t : vec) {
      uint32_t j = t.id_;
      // 第j条边的时间关系
      time_pair elem = edges_time[j];
      bool is_done = false;
      for (auto &it : table) {
        if (Is_Overlapping(elem, it.second)) {
          // 如果发现重叠
          is_done = true;
          it.second.first = std::min(elem.first, it.second.first);
          it.second.second = std::max(elem.second, it.second.second);
          auto part_num = it.first;
          res.vertex_partition_[i].part_[part_num].insert(j);
          res.vertex_partition_[i].map_[j] = part_num;
          break;
        }
      }
      if (!is_done) {
        // 没有重叠，新建一个分区
        table[global_part_idx] = elem;
        if (res.vertex_partition_[i].part_.size() <= global_part_idx) {

          // 初始为空，新建一个
          if (res.vertex_partition_[i].part_.empty()) {
            res.vertex_partition_[i].resize(1);
          } else {
            // 否则2倍扩容
            res.vertex_partition_[i].resize(
                res.vertex_partition_[i].part_.size() * 2);
          }
        }
        res.vertex_partition_[i].part_[global_part_idx].insert(j);
        res.vertex_partition_[i].map_[j] = global_part_idx;
        res.vertex_partition_[i].part_num++;
        global_part_idx++;
      }
    }
  }
  timer.end();
  std::cout << "end partition, time = " << timer.GetTimeConsuming() << "\n";
  return res;
}

} // namespace tbp